package Leetcode.图;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/9/10 16:49
 * @Description:
 * 现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。
 *
 * 返回图中 最短 环的长度。如果不存在环，则返回 -1 。
 *
 * 环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。
 *
 * 输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
 * 输出：3
 * 解释：长度最小的循环是：0 -> 1 -> 2 -> 0
 */

public class 图中的最短环 {
    private List<Integer>[] graph;
    private int[] dis; // dis[i] 表示从 start 到 i 的最短路长度

    public int findShortestCycle(int n, int[][] edges) {
        graph = new ArrayList[n];
        Arrays.setAll(graph, e -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            graph[x].add(y);
            graph[y].add(x); // 建图
        }
        dis = new int[n];

        int ans = Integer.MAX_VALUE;
        // 枚举每个起点跑 BFS
        for (int i = 0; i < n; ++i) {
            ans = Math.min(ans, bfs(i));
        }

        return ans < Integer.MAX_VALUE ? ans : -1;
    }

    private int bfs(int start) {
        // 初始化答案为最大整数值，表示初始时没有找到环
        int ans = Integer.MAX_VALUE;
        // 使用-1填充距离数组，表示所有顶点都未被访问
        Arrays.fill(dis, -1);
        // 起始顶点的距离设置为0
        dis[start] = 0;
        // 创建一个队列，用于进行广度优先搜索
        Queue<int[]> que = new ArrayDeque<>();
        // 将起始顶点和其前驱顶点（这里用-1表示没有前驱）加入队列
        que.add(new int[]{start, -1});

        // 当队列不为空时，继续广度优先搜索
        while (!que.isEmpty()) {
            // 从队列中取出当前顶点和其前驱顶点
            int[] p = que.poll();
            int curV = p[0], far = p[1];

            // 遍历当前顶点的所有邻接顶点
            for (int neighV : graph[curV]) {
                // 如果邻接顶点未被访问过
                if (dis[neighV] < 0) {
                    // 设置邻接顶点的距离为当前顶点距离加1
                    dis[neighV] = dis[curV] + 1;
                    // 将邻接顶点和当前顶点（作为前驱）加入队列
                    que.add(new int[]{neighV, curV});
                } else if (neighV != far) {
                    // 如果邻接顶点已经被访问过，并且不是当前顶点的前驱顶点
                    // 说明找到了一个环，计算环的长度并更新答案
                    ans = Math.min(ans, dis[curV] + dis[neighV] + 1);
                }
            }
        }
        // 返回找到的最短环的长度，如果没有找到环则返回Integer.MAX_VALUE
        return ans;
    }


}
